package problem733;

//733.图像渲染
//https://leetcode.cn/problems/flood-fill/description/

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        Queue<int[]> queue = new LinkedList<>();
        int n = image.length;
        int m = image[0].length;
        boolean[][] st = new boolean[n][m];
        st[sr][sc] = true;
        int t = image[sr][sc];
        queue.add(new int[]{sr,sc});
        
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            image[x][y] = color;
            for(int i = 0; i<4; i++) {
                int dx = x + xx[i];
                int dy = y + yy[i];
                if(dx>=0 && dx <n && dy>=0 && dy<m && image[dx][dy] == t && !st[dx][dy]) {
                    st[dx][dy] = true;
                    queue.add(new int[]{dx, dy});
                }
            }
            
        }
        return image;
    }
}